:- module(regex).
:- export split / 4.
:- export matchall / 4.
:- export matchsub / 4.
:- export match / 4.
:- export match / 3.
:- export match / 2.
:- export compile_pattern / 3.
:- comment(summary, "Interface to POSIX regular expression handling").
:- comment(author, "J Chamois").
:- comment(date, "$Date: 2004/11/12 18:55:21 $").
:- comment(copyright, "Public domain").
:- comment(desc, html("\n    This library implements an ECLiPSe API for POSIX 1003.2 regular\n    expressions (on Unix systems it calls the regular expression\n    functions from the standard library, on Windows it uses Henry\n    Spencer's regex library version 3.8).\n\n    <H3>Regular Expressions</H3>\n    This is just a very brief summary of the essentials.  For details\n    of regular expressions see any POSIX regex(7) man page.\n    Two types of regular expressions are supported:\n    <DL>\n    <DT>Extended Regular Expressions (the default)</DT>\n\t<DD>These are described below and correspond essentially to those\n\tunderstood by the UNIX egrep command.</DD>\n    <DT>Basic Regular Expressions</DT>\n\t<DD>These correspond essentially to those in the UNIX ed editor\n\tor the grep command, and are mostly obsolete.</DD>\n    </DL>\n    Note that our choice of default differs from the POSIX 1003.2 C API.\n\n    <H4>Characters</H4>\n    Every character stands for itself, except for the characters\n    ^.[$()|*+?{\\ which must be escaped with a \\ to prevent\n    them from having special meaning.\n    <DL>\n    <DT>.</DT>\n\t<DD>Matches any character</DD>\n    <DT>[aeiou]</DT>\n\t<DD>Matches any of the characters between the bracktes</DD>\n    <DT>[^aeiou]</DT>\n\t<DD>Matches any character except those listed</DD>\n    <DT>[a-z0-9]</DT>\n\t<DD>Matches any character in the given ranges</DD>\n    </DL>\n\n    <H4>Anchors</H4>\n    <DL>\n    <DT>^</DT>\n\t<DD>Matches at the beginning of the string (or line)</DD>\n    <DT>$</DT>\n\t<DD>Matches at the end of the string (or line)</DD>\n    </DL>\n\n    <H4>Repetition</H4>\n    <DL>\n    <DT>?</DT>\n\t<DD>Matches the preceding element 0 or 1 times</DD>\n    <DT>*</DT>\n\t<DD>Matches the preceding element 0 or more times</DD>\n    <DT>+</DT>\n\t<DD>Matches the preceding element 1 or more times</DD>\n    <DT>{3}</DT>\n\t<DD>Matches the preceding element 3 times</DD>\n    <DT>{1,3}</DT>\n\t<DD>Matches the preceding element 1 to 3 times</DD>\n    </DL>\n\n    <H4>Grouping</H4>\n    <DL>\n    <DT>(subexpr)</DT>\n\t<DD>Matches the parenthesized expression. This grouping is used\n\tin connection with the repetition operators, or for indicating \n\tsubexpressions whose matches are to be captured and returned</DD>\n    <DT>(one|two|three)</DT>\n\t<DD>Matches any of the alternative expressions</DD>\n    </DL>\n\n    <H3>Options</H3>\n    Most of the predicates in this library accept a list of options.\n    The accepted options are:\n    <DL>\n    <DT><TT>basic</TT></DT>\n\t<DD>Interpret the pattern as a Basic Regular Expression, rather\n\tthan the default Extended Regular Expression.</DD>\n    <DT><TT>extended</TT></DT>\n\t<DD>Interpret the pattern as an Extended Regular Expression\n\t(this flag is redundant since this is the default).</DD>\n    <DT><TT>icase</TT></DT>\n\t<DD>Ignore case when matching.</DD>\n    <DT><TT>newline</TT></DT>\n\t<DD>Treat newlines specially, i.e. don't treat them as normal\n\tcharacters and make ^ match after a newline and $ before a newline.\n\tBy default, newlines are treated as ordinary characters.</DD>\n    <DT><TT>notbol</TT></DT>\n\t<DD>Don't interpret the beginning of the string as the beginning\n\tof a line, i.e. don't let ^ match there.</DD>\n    <DT><TT>noteol</TT></DT>\n\t<DD>Don't interpret the end of the string as the end of a line,\n\ti.e. don't let $ match there.</DD>\n\t<DD></DD>\n    </DL>\n    <H3>Shortcomings</H3>\n    <OL>\n    <LI>\n    Due to limitations of the underlying implementation, the predicates\n    in this library do not handle embedded NUL characters in strings correctly\n    (they are interpreted as the end of the string).\n    <LI>\n    POSIX regular expressions don't seem to have a notion of  \"noncapturing\n    parentheses\", i.e. parentheses that are only used for grouping, not for\n    indicating that one wants to capture the matching substring.\n    <LI>\n    In an environment like ECLiPSe, one would like to be able to do things like\n    <PRE>\n\t?- ideal_match(\"(/[^/]*)+\", \"/usr/local/eclipse\", L).\n\tL = [\"/usr\", \"/local\", \"/eclipse\"]\n\tYes\n    </PRE>\n    i.e. capture every instance of a matching subexpression.  There seems\n    to be no way to do that with a POSIX regexp implementation.\n    </OL>\n")).
:- comment(compile_pattern / 3, [summary : "Precompile a pattern for repeated use", args : ["Pattern" : "A string", "Options" : "List of atoms", "CompiledPattern" : "Output: a compiled pattern handle"], amode : compile_pattern(+, +, -), fail_if : "None", see_also : [library(regex), match / 2, match / 3, match / 4, matchsub / 4, matchall / 4], desc : html("\n\tAll matching predicates in this library accept either a regular\n\texpression in string form, or a precompiled regular expression.\n\tThe matching predicates will execute faster if invoked with a\n\tprecompiled pattern instead of the string.  Whenever a pattern\n\tneeds to be matched more than once, it will typically be more\n\tefficient to work with a precompiled pattern.\n\t<P>\n    \tOptions is a (possibly empty) list of atomic option names,\n\tas described in the library(regex) page.  The options give here\n\tshould be the same as the ones given to the matching-predicates later.\n\t<P>\n\tThe space consumed by the compiled pattern will be automatically\n\treclaimed on failure, or on garbage collection when no longer needed.\n    "), eg : "\n    ?- compile_pattern(\"ab+a\", [], C),\n       match(C, \"bbabbbaab\", [], M1),\n       match(C, \"abacus\", [], M2).\n\n    C = 'HANDLE'(16'00025c60)\n    M1 = \"abbba\"\n    M2 = \"aba\"\n    Yes\n    "]).
:- comment(match / 2, [summary : "A substring of String matches the regular expression Pattern", args : ["Pattern" : "A string (or a compiled pattern handle)", "String" : "A string"], amode : match(+, +), fail_if : "String does not match Pattern", desc : html("\n\tSucceeds if all or a substring of String matches the regular\n\texpression Pattern. For the description of regular expressions\n\tsee the library(regex) page.\n\t<P>\n    \tEquivalent to match(Pattern, String, []).\n    "), see_also : [library(regex), match / 3, match / 4, matchsub / 4, matchall / 4, split / 4, compile_pattern / 3], eg : "\n    ?- match(\"aca\", \"abracadabra\").\n    Yes\n\n    ?- match(\"^a[cd]a$\", \"abracadabra\").\n    No\n\n    ?- match(\"^a[cd]a$\", \"ada\").\n    Yes\n    "]).
:- comment(match / 3, [summary : "A substring of String matches the regular expression Pattern", args : ["Pattern" : "A string (or a compiled pattern handle)", "String" : "A string", "Options" : "List of atoms"], amode : match(+, +, +), fail_if : "String does not match Pattern", see_also : [library(regex), match / 2, match / 4, matchall / 4, matchsub / 4, split / 4, compile_pattern / 3], desc : html("\n\tSucceeds if all or a substring of String matches the regular\n\texpression Pattern. For the description of regular expressions\n\tsee the library(regex) page.\n\t<P>\n    \tOptions is a (possibly empty) list of atomic option names,\n\tas described in the library(regex) page.\n    "), eg : "\n    ?- match(\"april\", \"April\", []).\n    No\n    ?- match(\"april\", \"April\", [icase]).\n    Yes\n\n    ?- match(\"(^(a[cd]a)$)+\", \"aca\\nada\", []).\n    No\n    ?- match(\"(^(a[cd]a)$)+\", \"aca\\nada\", [newline]).\n    Yes\n\n    ?- match(\"\\\\<word\\\\>\", \"a word only\", [basic]).\n    Yes\n    ?- match(\"\\\\<word\\\\>\", \"not words though\", [basic]).\n    No\n    "]).
:- comment(match / 4, [summary : "Match is the first substring of String that matches the regular expression Pattern", args : ["Pattern" : "A string (or a compiled pattern handle)", "String" : "A string", "Options" : "List of atoms", "Match" : "Output: a string"], amode : match(+, +, +, -), fail_if : "String does not match Pattern", see_also : [library(regex), match / 2, match / 3, matchsub / 4, matchall / 4, compile_pattern / 3], desc : html("\n\tSucceeds if all or a substring of String matches the regular\n\texpression Pattern. For the description of regular expressions\n\tsee the library(regex) page.\n\t<P>\n    \tOptions is a (possibly empty) list of atomic option names,\n\tas described in the library(regex) page.\n\t<P>\n\tMatch is bound to the first substring of String which matches\n\tPattern.\n\t<P>\n\tNote that this predicate does not return any information about\n\tmatching (parenthesised) sub-expressions!\n    "), eg : "\n    ?- match(\"<[a-z]+>\", \"Text with <HTML> tags\", [icase], M).\n    M = \"<HTML>\"\n    Yes\n    "]).
:- comment(matchall / 4, [summary : "AllMatches is a list of substrings of String which match the regular expression Pattern", args : ["Pattern" : "A string (or a compiled pattern handle)", "String" : "A string", "Options" : "List of atoms", "AllMatches" : "Output: List of strings"], amode : matchall(+, +, +, -), fail_if : "None", see_also : [library(regex), match / 2, match / 3, match / 4, split / 4, compile_pattern / 3], desc : html("\n\tThis predicates always succeeds.\n\t<P>\n    \tOptions is a (possibly empty) list of atomic option names,\n\tas described in the library(regex) page.\n\t<P>\n\tAllMatches is bound to a list of strings. If the input string String\n\tdoes not match the pattern, the list is empty. Otherwise the list\n\tcontains substrings of String which match the entire pattern,\n\tordered according to their occurrence within String. No overlapping\n\tmatches are returned, i.e. the next match is found by examining the\n\tremainder of String after the previous match.\n\t<P>\n\tNote that this predicate does not return any information about\n\tmatching (parenthesised) sub-expressions!\n    "), eg : "\n    ?- matchall(\"[0-9]+\", \" blue 27 red123 green99\", [], L).\n    L = [\"27\", \"123\", \"99\"]\n    Yes\n\n    ?- matchall(\"([0-9]+|[^0-9]+)\", \" blue 27 red123 green99\", [], L).\n    L = [\" blue \", \"27\", \" red\", \"123\", \" green\", \"99\"]\n    Yes\n    "]).
:- comment(matchsub / 4, [summary : "A substring of String matches the regular expression Pattern and SubMatches are matching sub-expressions", args : ["Pattern" : "A string (or a compiled pattern handle)", "String" : "A string", "Options" : "List of atoms", "SubMatches" : "Output: List of strings"], amode : matchsub(+, +, +, -), fail_if : "String does not match Pattern", see_also : [library(regex), match / 2, match / 3, match / 4, compile_pattern / 3], desc : html("\n\tSucceeds if all or a substring of String matches the regular\n\texpression Pattern. For the description of regular expressions\n\tsee the library(regex) page.\n\t<P>\n    \tOptions is a (possibly empty) list of atomic option names,\n\tas described in the library(regex) page.\n\t<P>\n\tSubMatches is bound to a list of strings, each corresponding to\n\ta parenthesized subexpression in Pattern. These subexpressions\n\tare ordered according to the position of their opening parenthesis\n\twithin the pattern. The matching string appears on the corresponding\n\tposition in the SubMatches list. Note that, if a subexpression matches\n\tseveral times, only the last match is returned.\n\t<P>\n    "), eg : "\n    ?- matchsub(\"Name:([^,]+), Age:([0-9]+),\", \"Name:Fred, Age:34,\", [], L).\n    L = [\"Fred\", \"34\"]\n    Yes\n    "]).
:- comment(split / 4, [summary : "Parts is a list of substrings, partitioning String according to Pattern", args : ["Pattern" : "A string (or a compiled pattern handle)", "String" : "A string", "Options" : "List of atoms", "Parts" : "Output: List of strings"], amode : split(+, +, +, -), fail_if : "None", see_also : [library(regex), matchall / 4, compile_pattern / 3, concat_string / 2, split_string / 4], desc : html("\n\tThis predicates always succeeds.\n\t<P>\n    \tOptions is a (possibly empty) list of atomic option names,\n\tas described in the library(regex) page.\n\t<P>\n\tParts is bound to a list of strings which are consecutive substrings\n\tof the input string String (i.e. concatenating this list using\n\tconcat_strings/2 will yield the original String). The list is\n\tconstructed such that it has an odd number of elements, where the\n\teven numbered elements match the pattern, and the odd numbered\n\telements contains those portions of String that did not match\n\tthe Pattern. Some of these substrings may be empty.\n\t<P>\n\tThis partitioning of the String can be used to construct a new\n\tstring with the matches replaced by something else. Use the\n\tfollowing code pattern:\n\t<PRE>\n\t    split(Pattern, String, Options, Parts),\n\t    (\n\t\tfromto(Parts, [NoMatch,Match|NMs], NMs, [Last]),\n\t\tfromto(Repl,  [NoMatch,Subst|NSs], NSs, [Last])\n\t    do\n\t\t%%% compute Subst from Match here %%%\n\t    ),\n\t    concat_string(Repl, NewString),\n\t</PRE>\n\t<P>\n\tNote that the split/4 predicate does not return any information about\n\tmatching (parenthesised) sub-expressions!\n    "), eg : "\n    ?- split(\"cad\", \"abracadabra\", [], Parts).\n    Parts = [\"abra\", \"cad\", \"abra\"]\n    Yes (0.00s cpu)\n\n    ?- split(\"bra\", \"abracadabra\", [], Parts).\n    Parts = [\"a\", \"bra\", \"cada\", \"bra\", \"\"]\n    Yes (0.00s cpu)\n\n    ?- split(\"bla\", \"abracadabra\", [], Parts).\n    Parts = [\"abracadabra\"]\n    Yes (0.00s cpu)\n\n    ?- split(\"a\", \"aaa\", [], Parts).\n    Parts = [\"\", \"a\", \"\", \"a\", \"\", \"a\", \"\"]\n    Yes (0.00s cpu)\n \n    ?- split(\"%[a-z]\", \"format %s %f=%d.\", [], Parts).\n    Parts = [\"format \", \"%s\", \" \", \"%f\", \"=\", \"%d\", \".\"]\n    Yes (0.00s cpu)\n\n\n    % With the following definition\n    replace(Pattern, New, String, NewString) :-\n\tsplit(Pattern, String, [], Parts),\n\t(\n\t    fromto(Parts, [NoMatch,_Match|NMs], NMs, [Last]),\n\t    fromto(Repl,  [NoMatch, Subst|NSs], NSs, [Last]),\n\t    param(New)\n\tdo\n\t    Subst = New\n\t),\n\tconcat_string(Repl, NewString).\n\n    ?- replace(\"2\", \"to\", \"2 be or not 2 be\", S).\n    S = \"to be or not to be\"\n    Yes (0.00s cpu)\n    "]).